//
// Created by 86152 on 2021/7/30.
//

#ifndef DATASTRUCTURE_PART2_H
#define DATASTRUCTURE_PART2_H


#include <iostream>
namespace part2{

/****************O(n) 删除数组中相同元素***************************/
    int delCommon(int* array, int n){
        int k = 0;
        for (int i = 0; i < n; ++i) {
            if (array[i] != array[k]){
                array[++k] = array[i];
            }
        }
        return k+1;
    }

    void Test_delCommon(){
        int a[11] = {1,1,1,2,2,3,3,4,4,5,5};
        int k = delCommon(a,11);
        for (int i = 0; i < k+1; ++i) {
            printf("%d ",a[i]);
        }
    }


/****************翻转链表***************************/
    typedef  struct Node{
        int data;
        Node* next;
    }Node;

    Node* reverLinkedList(Node &root){
        if (root.next == nullptr) return &root;  // 如果是最后一个节点，直接返回
        // 如果不是最后一个节点，递归
        Node* tail = reverLinkedList(*root.next);
        // 翻转当前节点
        root.next->next = &root;
        root.next = nullptr;
        return tail;
    }

    void Test_reverLinkedList(){
        Node a1;
        a1.data = 1;

        Node a2;
        a2.data = 2;

        Node a3;
        a3.data = 3;

        Node a4;
        a4.data = 4;

        a1.next = &a2;
        a2.next = &a3;
        a3.next = &a4;
        a4.next = nullptr;

        Node* a = reverLinkedList(a1);
        while (a != nullptr){
            std::cout << a->data << " ";
            a = a->next;
        }
        std::cout << std::endl;
    }

    // 翻转数组
    void rever_array(int* array, int length){
        for (int i = 0; i < length / 2; ++i) {
            int t = array[i];
            array[i] = array[length - 1 - i];
            array[length - i - 1] = t;
        }
    }

    void swap_sub_array(int* array, int len1, int len2){
        rever_array(array,len1);
        rever_array(array + len1, len2);
        rever_array(array,len1 + len2);
    }

    void Test_swap_sub_array(){
        int array[10] = {0,1,2,3,4,5,6,7,8,9};
        swap_sub_array(array,4,6);

        for (int i = 0; i < 10; ++i) {
            std::cout << array[i] << " ";
        }
        std::cout << std::endl;
    }

}


#endif //DATASTRUCTURE_PART2_H
